package stu.day50;

import java.util.HashMap;

public class hw1 {
    public boolean isBipartite(int[][] graph) {

        int n = graph.length;

        HashMap<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<n;i++){
            if(!map.containsKey(i)){
                if(!fun(graph,map,1,i)) return  false;
            }
        }

        return true;
    }


    public boolean fun(int[][] graph, HashMap<Integer,Integer> map,int num,int j){
        if(map.containsKey(j)) return map.get(j)==num;

        map.put(j,num);
        for (int i:graph[j]){
            if(!fun(graph,map,-num,i)){
                return false;
            }
        }

        return true;

    }


    public static void main(String[] args) {
        //[[1],[0,3],[3],[1,2]]
        int[][] g = new int[][]{{1},{0,3},{3},{1,2}};
        hw1 h =new hw1();
        System.out.println(h.isBipartite(g));

    }


}
